package leetcode.biweekly.week103;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;
//H.print(l);
//H.print(r);
//Solution4Test
public class Solution4 {

	public long countOperationsToEmptyArray(int[] nums) {
		int n = nums.length;
		TreeSet<Integer> ts = new TreeSet<>();
		for (int num : nums) {
			ts.add(num);
		}
		TreeMap<Integer, Integer> tm = new TreeMap<>();
		int id = 1;
		for (int num : ts) {
			tm.put(num, id++);
		}
		for (int i = 0; i < n; i++) {
			nums[i] = tm.get(nums[i]);
		}
		int[] r = new int[n];
		int[] l = new int[n];
		Record record = new Record(n);
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < n; i++) {
			int num = nums[i];
			int less = record.query(num - 1);
			int L = num - 1;
			int R = n - num;
			// 1,2,3,4
			l[i] = i - less;
			r[i] = R - l[i];
			record.add(num);
			map.put(num, i);
		}

		long ans = 0;
		for (int i = 0; i < n; i++) {
			int num = nums[i];
			int less1 = num - 1;
			int id1 = map.getOrDefault(less1, -1);
			if (id1 == -1) {
				ans += l[i] + 1;
			} else {
				if (id1 > i) {
					ans += l[i] + r[id1] + 1;
				} else {
					ans += r[id1] - r[i];
				}
			}
		}
		return ans;
	}

	class Record {
		int len;
		int[] arr;

		public Record(int n) {
			len = n + 2;
			arr = new int[len];
		}

		public void add(int num) {
			while (num < len) {
				arr[num]++;
				num += this.lowbit(num);
			}
		}

		public void sub(int num) {
			while (num < len) {
				arr[num]--;
				num += this.lowbit(num);
			}
		}

		public int query(int num) {
			int ans = 0;
			while (num > 0) {
				ans += arr[num];
				num -= this.lowbit(num);
			}
			return ans;
		}

		public int lowbit(int num) {
			return num & -num;
		}
	}

}
